package codetop.microsoft.T739;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: 18362
 * @Create: 2022-08-15 22:32:13 星期一
 */
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        Deque<Integer> dq = new LinkedList<>();
        for (int i=temperatures.length-1; i>=0; --i) {
            while (!dq.isEmpty() && temperatures[dq.getLast()] <= temperatures[i])
                dq.removeLast();
            res[i] = dq.isEmpty() ? 0 : dq.getLast() - i;
            dq.addLast(i);
        }
        return res;
    }
}